﻿using System;
using System.Collections.Generic;
using System.Globalization;
using System.Linq;
using System.Numerics;

namespace SpotifyTechPuzzles.TicketLottery
{
    /// <summary>
    /// Spec: Hg$\Docs\Ticket Lottery Puzzle - Spotify.htm
    /// </summary>
    public class GroupGetsTicketsProbabilityCalculator
    {
        private readonly uint numberOfPeopleWhoEnteredLottery;
        private readonly uint totalNumberOfWinnersDrawn;
        private readonly uint numberOfTicketsEachWinnerIsAllowedToBuy;
        private readonly uint numberOfPeopleInGroup;

        public GroupGetsTicketsProbabilityCalculator(string input)
        {
            // no validation; assuming input according to spec: m n t p
            // where 1 ≤ m ≤ 1000, 1 ≤ n ≤ m, 1 ≤ t ≤ 100, 1 ≤ p ≤ m
            var inputAsDecimals = input.Split(' ').Select(AsUInt);
            numberOfPeopleWhoEnteredLottery = inputAsDecimals.ElementAt(0);
            totalNumberOfWinnersDrawn = inputAsDecimals.ElementAt(1);
            numberOfTicketsEachWinnerIsAllowedToBuy = inputAsDecimals.ElementAt(2);
            numberOfPeopleInGroup = inputAsDecimals.ElementAt(3);
        }

        public string Calculate()
        {
            if (ImpossibleToWin())
                return "0";

            if (EverybodyWins())
                return "1";

            var totalProbability = RequiredNoOfWins.To(numberOfPeopleInGroup)
                .Select(GetProbability)
                .Sum();

            return GetAsString(totalProbability);
        }

        private bool ImpossibleToWin()
        {
            return RequiredNoOfWins > totalNumberOfWinnersDrawn;
        }

        private bool EverybodyWins()
        {
            return numberOfPeopleWhoEnteredLottery == totalNumberOfWinnersDrawn 
                || totalNumberOfWinnersDrawn + numberOfPeopleInGroup >= numberOfPeopleWhoEnteredLottery + RequiredNoOfWins;
        }

        /// <summary>
        /// Specification: http://en.wikipedia.org/wiki/Hypergeometric_distribution#Application_and_example
        /// </summary>
        private decimal GetProbability(uint noOfWinsOfGroup)
        {
            var probability = (decimal)(numberOfPeopleInGroup.Choose(noOfWinsOfGroup)
                                        * (numberOfPeopleWhoEnteredLottery - numberOfPeopleInGroup)
                                              .Choose(totalNumberOfWinnersDrawn - noOfWinsOfGroup))
                              / (decimal)numberOfPeopleWhoEnteredLottery.Choose(totalNumberOfWinnersDrawn);

            return probability;
        }

        private uint RequiredNoOfWins
        {
            get
            {
                return (uint) Math.Ceiling((decimal) numberOfPeopleInGroup / numberOfTicketsEachWinnerIsAllowedToBuy);
            }
        }

        private static string GetAsString(decimal arg)
        {
            const int DECIMALS = 10;
            var argAsString = arg.RoundTo(DECIMALS).ToString(CultureInfo.InvariantCulture);

            return argAsString;
        }

        private static uint AsUInt(string arg)
        {
            return uint.Parse(arg);
        }
    }

    public static class ProbabilityCalculatorExtensions
    {
        internal static IEnumerable<uint> To(this uint @this, uint to)
        {
            for (var i = @this; i <= to; i++)
                yield return i;
        }

        internal static decimal RoundTo(this decimal @this, byte decimals)
        {
            return decimal.Round(@this, decimals);
        }

        /// <summary>
        /// Definition: http://mathworld.wolfram.com/BinomialCoefficient.html
        /// </summary>
        internal static BigInteger Choose(this uint n, uint k)
        {
            if (n == k)
                return BigInteger.One;

            return n.Factorial() / ( (n - k).Factorial() * k.Factorial() );
        }

        /// <summary>
        /// Definition: http://mathworld.wolfram.com/Factorial.html
        /// </summary>
        public static BigInteger Factorial(this uint @this)
        {
            if (@this == 0u || @this == 1u)
                return BigInteger.One;

            return @this * Factorial(@this - 1);
        }
    }
}